The present invention relates to an image processing technique for making a fast search of a search image for a portion similar to a reference template image.
In FIGS. 1A through 1C there is schematically shown a reference correlation matching scheme that has been widely used to search an image for an image portion having the highest degree of similarity to a reference template image. According to the normalized correlation matching scheme, a reference template image g of a size P.times.Q such as shown in FIG. 1B is moved in such a search image f of a size X.times.Y as shown in FIG. 1A in the x and y directions repeatedly as depicted in FIG. 1C to find a position where the highest normalized correlation is provided between the search image f and the template image G. In this example, reference template images g.sub.0, g.sub.1, . . . , g.sub.M, which are M+1 different views of an object image to be searched, are each matched with the object image in the search image f to detect a position where they show the highest degree of similarity.
Turning next to FIG. 2, the work flow of such a conventional template matching scheme will be described. The matching starts with setting a matching start position (x=0, y=0) in step S1. In step S2 a position of coordinates (x,y) in the search image f is set as a reference position for matching with the template image and the following normalized correlations between the search image f and the M+1 reference template images g.sub.0, g.sub.1, . . . , g.sub.M are calculated: EQU (fx,y!,g.sub.0), (fx,y!,g.sub.1), . . . , (fx,y!, g.sub.M)
Then, in step S3 a check is made to determine if the reference matching position (x,y) has reached the final position (x=X-P,y=Y-Q). If not, the search proceeds to the next position in the search image f in step S4, and steps S1 through S4 are carried out again. When it is decided in step S3 that the final matching position (X-P,Y-Q) has been reached, the processing goes to step S5 in which the position (x,y) is output where the highest one of normalized correlations is obtained by scanning an image region (O.ltoreq.x.ltoreq.X-P, O.ltoreq.y.ltoreq.Y-Q).
With such a conventional template matching scheme, however, individual fluctuations of the object to be searched (hereinafter referred to as a search object) (e.g., deformations such as distortions, dents or pattern variations, or fluctuations of inspection environments (such as changes in illumination and in the position relative to the position of observation) give rise to problems such as a failure of search, an erroneous or incorrect search and a decrease in the accuracy of the position of search in the case of using one reference template image for matching with the search object. To solve these problems, it is conventional to perform matching of the search image with a plurality of reference template images corresponding to estimated fluctuations of the search object so as to detect the image position where the maximum correlation value is provided.
In this instance, the template images for matching with the search image need to be prepared taking into account factors in the fluctuations of the object to be detected and the fluctuation ranges. The prior art scheme uses a large number of such reference template images to cover the fluctuation ranges and to deal with small fluctuations. Another problem of the conventional scheme is the large amount of time that is required to match every template image with the search image over the entire region thereof (for obtaining correlation values). In addition to these disadvantages, there are cases where it is practically impossible to predict and prepare a large number of template images that cover the fluctuation ranges.
As described above, the prior art scheme involves estimation of fluctuations of the object to be searched and discrete preparation of a large number of template images corresponding to the estimated fluctuations--this gives rise to the problems of low reliability of the search results due to the suitability of representation by the template image and low search efficiency because of the use of a large number of template images.